package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 有一个二维数组，每个位置的数据都大于等于0
 * 从[0,0]位置开始出发，只能向右或者向下走
 * 要求从[0,0]位置走到[n-1][n-1]位置的最小距离
 */
public class 二维数组最小距离累加和 {
    public static void main(String[] args) {
        int[][] map = new int[][]{};
        int distance = minDistance(map);
    }

    private static int minDistance(int[][] map) {
        if (map == null) {
            return -1;
        }

        int yN = map.length;
        int xN = map[0].length;
        return process(map, 0, 0, xN, yN);
    }

    /**
     * process 方法返回的是从[0,0]位置到x,y位置的最短距离
     *
     * @param map
     * @param x
     * @param y
     * @param xN
     * @param yN
     * @return
     */
    private static int process(int[][] map, int x, int y, int xN, int yN) {
//        if (x = xN) {
//        }

        int p1 = process(map, x - 1, y, xN, yN) + map[x][y];
        int p2 = process(map, x, y - 1, xN, yN) + map[x][y];
        return Math.min(p2, p1);
    }

    /**
     * process 方法返回的是从[0,0]位置到x,y位置的最短距离
     *
     * @param map
     * @return
     */
    private static int dp(int[][] map) {
        int yN = map.length;
        int xN = map[0].length;
        int dp[][] = new int[yN + 1][xN + 1];
        dp[0][0] = map[0][0];// 根据提议可知

        for (int i = 1; i < yN; i++) {
            dp[i][0] = dp[i - 1][0] + map[i][0];
        }
        for (int i = 1; i < xN; i++) {
            dp[0][i] = dp[0][i - 1] + map[0][i];
        }


        for (int i = 1; i < yN; i++) {
            for (int j = 1; j < xN; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+map[i][j];
            }
        }

        return dp[yN][xN];
    }
}
